package 树;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <p>
 * https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 * </p>
 *
 * @author AJun
 * @since 2020/8/22
 */
public class _662_二叉树最大宽度 {

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        // 根节点编号为 0
        root.val = 0;
        queue.add(root);

        int sum;
        int ans = 0;
        while (!queue.isEmpty()) {
            sum = queue.size();
            // 队头和队尾的编号值求差用来更新宽度
            ans = Math.max(ans, queue.getLast().val - queue.getFirst().val + 1);
            // 一次处理一层，进入这个循环前队列中是一层的所有非空节点
            while (sum > 0) {
                TreeNode temp = queue.remove();

                // 子节点入队前修改 val, val = 满二叉树中节点编号
                if (temp.left != null) {
                    queue.add(temp.left);
                    temp.left.val = temp.val * 2 + 1;
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                    temp.right.val = temp.val * 2 + 2;
                }
                sum--;
            }
        }
        return ans;
    }

}
